package gold.digger;

import gold.utils.InputUtil;
import gold.vo.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1008 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public TreeNode bstFromPreorder(int[] preorder) {
            return bstFromPreorderRecur(preorder, 0, preorder.length - 1);
        }

        public TreeNode bstFromPreorderRecur(int[] preorder, int start, int end) {
            if (end < start) return null;
            if (end == start) return new TreeNode(preorder[start]);

            TreeNode curRoot = new TreeNode(preorder[start]);
            int rightStart = start + 1;
            while (rightStart <= end && preorder[rightStart] < preorder[start]) ++rightStart;
            curRoot.left = bstFromPreorderRecur(preorder, start + 1, rightStart - 1);
            curRoot.right = bstFromPreorderRecur(preorder, rightStart, end);
            return curRoot;
        }
    }

    public void run() {
        Solution solution = new Solution();
//        int[] pre = InputUtil.toIntegerArray("[8,5,1,7,10,12]");
        int[] pre = InputUtil.toIntegerArray("[4,2]");
        final TreeNode treeNode = solution.bstFromPreorder(pre);
        System.out.println(treeNode);
    }

    public static void main(String[] args) throws Exception {
        LC1008 an = new LC1008();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
